// export const getAllChildSeq = (str: string) => {
//   const len = str.length;
//   const children: string[] = [];
  
//   const getSubSeq = (index: number, preSub: string) => {
//     if (index === len) {
//       if (preSub) {
//         children.push(preSub);
//       }
//     } else {
//       getSubSeq(index + 1, preSub);
//       getSubSeq(index + 1, preSub + str[index]);
//     }
//   };

//   getSubSeq(0, '');
//   return children;
// };

export const getAllChildSeq = (str: string) => {  
  const getSubSeq = (str: string): string[] => {
    if (str.length === 0) {
      return [];
    }
    if (str.length === 1) {
      return [str];
    } else {
      const head: string = str[0];
      let children = getSubSeq(str.slice(1));
      const result: string[] = [head, ...children];
      
      children.forEach(item => {
        result.push(`${head}${item}`);
      });

      return result;
    }
  };
  
  return getSubSeq(str);
};

export const getLongestChildSeq = (str1: string, str2: string) => {
  const str1Arr = str1.split('');
  const str2Arr = str2.split('');
  const matrix: string[][] = [];

  for (let i = 0; i < str1Arr.length; i++) {
    const row = [];
    const rowChar = str1Arr[i];
    
    matrix.push(row);

    for (let j = 0; j < str2Arr.length; j++) {
      const colChar = str2Arr[j];

      const preStrs = [
        matrix[i - 1]?.[j - 1] ?? '',
        matrix[i - 1]?.[j] ?? '',
        matrix[i]?.[j - 1] ?? ''
      ]; 

      let preStr = '';
      preStrs.forEach(str => {
        str.length > preStr.length && (
          preStr = str
        );
      });

      if (rowChar === colChar) {
        matrix[i][j] = (matrix[i - 1]?.[j - 1] ?? preStr) + colChar;
      } else {
        matrix[i][j] = preStr;
      }
    }
  }
  
  return matrix[str1Arr.length - 1]?.[str2Arr.length - 1] ?? '';
};
